#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
const int N = 1e3 + 10;
int g[N][N];
bool st[N][N];

class Solution {
public:
    int bfs(vector<vector<int> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int cnt = 0;
        queue<PII> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({ i,j });
                    st[i][j] = true;
                }
                else if (grid[i][j] == 1)cnt++;
            }
        }
        int t = -1;
        while (!q.empty()) {
            int sz = q.size();
            // cout<<sz<<endl;
            for (int i = 0; i < sz; i++) {
                auto it = q.front();
                q.pop();
                int x = it.first;
                int y = it.second;
                for (int j = 0; j < 4; j++) {
                    int a = x + dx[j];
                    int b = y + dy[j];
                    if (a >= 0 && a < m && b >= 0 && b < n && !st[a][b] && grid[a][b] == 1) {
                        g[a][b] = 2;
                        cnt--;
                        q.push({ a,b });
                        st[a][b] = true;
                    }
                }
            }
            t++;
        }

        if (cnt)return -1;
        return t;

    }
    int rotApple(vector<vector<int> >& grid) {
        return bfs(grid);
    }
};